import java.util.PriorityQueue;
import java.util.Iterator;

public class Congress {
	int conSeats;
	//MaxPQ<State> queue;
	PriorityQueue<State> queue;

	public Congress(){

	}

	public static void main (String args[]){
		Congress c = new Congress();		
		if(args.length != 1) {
			System.out.println("Parameters goddammit");
			return;
		} 
		c.readFromFile (args[0]);
		c.apportion();
	}
	
	/*
	 * A state has a name, population and is initialized with one seat.
	 */
	private class State implements Comparable<State> {
		private String name;
		private int pop;
		private int seats=0;
		private int prior;

		public State (String n, int p) {
			this.name = n;
			this.pop = p;
			addSeat();
		}
		
		public void addSeat () {
			this.prior = (int) ((double) pop/Math.sqrt(++seats*(seats+1)));
		}

		public String getName() {
			return this.name;
		}

		public int getSeats() {
			return seats;
		}

		public int getPrior() {
			return this.prior;
		}

		public int compareTo(State o){
			//return this.prior - o.getPrior();
			return o.getPrior() - this.prior; //reversed because javas priorityqueue has the smallest element in the root.
		}
	}

	public void readFromFile(String f) {
		In read = new In(f);
		int sz = Integer.parseInt(read.readLine());
		//queue = new MaxPQ<State>(sz);
		queue = new PriorityQueue<State>(sz);
		conSeats = Integer.parseInt(read.readLine());

		for (int i=0; i<sz; i++) {
			String s = read.readLine();
			int p = Integer.parseInt(read.readLine());
			//queue.insert(new State(s, p));
			queue.add(new State(s, p));
		}
	}

	public void apportion() {
		int assigns = conSeats - queue.size();
		for (int i=0; i<assigns; i++) {
			//State s = queue.eatMax();
			State s = queue.remove();
			s.addSeat();
			//queue.insert(s);
			queue.add(s);
		}
		
		//State[] ss = (State[])queue.getList();
		//for (int i=1; i<ss.length; i++) {
		//	System.out.println(ss[i].getName() +"\n" + ss[i].getSeats());
		//}
		
		Iterator<State> it = queue.iterator();
		while (it.hasNext()) {
			State st = it.next();
			System.out.println(st.getName() + "\t" + st.getSeats());
		}
	}
}
